<!DOCTYPE HTML>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" /> 
    <title> - 天地维杰网</title>
    <meta name="keywords" content="系统架构,shutdown,不与天斗,Domino,博客,程序员,架构师,笔记,技术,分享,java,Redis">
    
    <meta property="og:title" content="">
    <meta property="og:site_name" content="天地维杰网">
    <meta property="og:image" content="/img/author.jpg"> 
    <meta name="title" content=" - 天地维杰网" />
    <meta name="description" content="天地维杰网 | 博客 | 软件 | 架构 | Java "> 
    <link rel="shortcut icon" href="http://www.shutdown.cn/img/favicon.ico" />
    <link rel="apple-touch-icon" href="http://www.shutdown.cn/img/apple-touch-icon.png" />
    <link rel="apple-touch-icon-precomposed" href="http://www.shutdown.cn/img/apple-touch-icon.png" />
    <link href="http://www.shutdown.cn/js/vendor/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
    <link href="http://www.shutdown.cn/js/vendor/fancybox/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />
    <link href="http://www.shutdown.cn/css/main.css" rel="stylesheet" type="text/css" />
    <link href="http://www.shutdown.cn/css/syntax.css" rel="stylesheet" type="text/css" />
    <script type="text/javascript" id="hexo.configuration">
  var NexT = window.NexT || {};
  var CONFIG = {
    scheme: 'Pisces',
    sidebar: {"position":"left","display":"post"},
     fancybox: true, 
    motion: true
  };
</script>
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-7826003325059020" crossorigin="anonymous"></script>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<div class="container one-collumn sidebar-position-left page-home  ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"> <div class="site-meta  custom-logo ">

  <div class="custom-logo-site-title">
    <a href="http://www.shutdown.cn"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">天地维杰网</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle">人如秋鸿来有信，事若春梦了无痕</p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
    <ul id="menu" class="menu">
      
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/redis/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-battery-full"></i> <br />Redis
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/java/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-coffee"></i> <br />java
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/linux/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-linux"></i> <br />linux
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/daily/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-bug"></i> <br />日常问题
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/spring/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-child"></i> <br />Spring和Springboot
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/mac/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-fire"></i> <br />Mac相关
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/middleware/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-gavel"></i> <br />中间件
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/jiagou/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-rocket"></i> <br />架构
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/python/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-ship"></i> <br />python
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/front/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-bolt"></i> <br />前端
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/jvm/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-balance-scale"></i> <br />jvm
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/c/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-battery-empty"></i> <br />c语言
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/web3/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-web3"></i> <br />web3
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/post/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/about/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />关于
          </a>
        </li>
      
      <li class="menu-item menu-item-search">
        <a href="javascript:;" class="popup-trigger"> <i class="menu-item-icon fa fa-search fa-fw"></i> <br /> 搜索</a>
      </li>
    </ul>
    <div class="site-search">
      <div class="popup">
 <span class="search-icon fa fa-search"></span>
 <input type="text" id="local-search-input">
 <div id="local-search-result"></div>
 <span class="popup-btn-close">close</span>
</div>

    </div>
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
<section id="posts" class="posts-expand">
  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
    <header class="post-header">
      <h1 class="post-title" itemprop="name headline">
        <a class="post-title-link" href="http://www.shutdown.cn/post/redis7.0%E6%96%B0%E7%89%B9%E6%80%A7-hashlistzset-%E7%9A%84-ziplist-%E6%9B%BF%E6%8D%A2%E4%B8%BA-listpack/" itemprop="url">
        
        </a>
      </h1>
      <div class="post-meta">
      <span class="post-time">
<span class="post-meta-item-icon">
    <i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">时间：</span>
<time itemprop="dateCreated" datetime="2016-03-22T13:04:35+08:00" content="0001-01-01">
    0001-01-01
</time>
</span> 
      
      
       <span>
&nbsp; | &nbsp;
<span class="post-meta-item-icon">
    <i class="fa fa-eye"></i>
</span>
<span class="post-meta-item-text">阅读：</span>
<span class="leancloud-visitors-count">1071 字 ~6分钟</span>
</span>
      </div>
    </header>
    <div class="post-body" itemprop="articleBody">
    

    

<blockquote>
<p><a href="https://blog.csdn.net/ldw201510803006/article/details/122420585">https://blog.csdn.net/ldw201510803006/article/details/122420585</a></p>
</blockquote>

<h1 id="前言">前言</h1>

<p>从 <strong>ziplist</strong> 到 <strong>quicklist</strong>，再到 <strong>listpack</strong> 结构；可以看到，初衷都是设计一款数据结构能够高效的使用内存。</p>

<p>ziplist 设计出的紧凑型数据块可以有效利用内存，但在更新上，由于每一个 entry 都保留了前一个 entry 的 prevlen 长度，因此在插入或者更新时可能会出现连锁更新，这是一个影响效率的大问题。</p>

<p>因此，接着又设计出 「链表 + ziplist」组成的 quicklist 结构来避免单个 ziplist 过大，可以有效降低连锁更新的影响面。</p>

<p>但 quicklist 本质上不能完全避免连锁更新问题，因此，又设计出与 ziplist 完全不同的内存紧凑型结构 listpack，继续往下看～</p>

<hr />

<h1 id="一-listpack是什么">一、listpack是什么？</h1>

<p>listpack 也叫<strong>紧凑列表</strong>，它的特点就是用一块连续的内存空间来紧凑地保存数据，同时为了节省内存空间，listpack 列表项使用了多种编码方式，来表示不同长度的数据，这些数据包括整数和字符串。</p>

<p>Redis源码对于listpack的解释为 A lists of strings serialization format，一个字符串列表的序列化格式，也就是将一个字符串列表进行序列化存储。Redis listpack可用于存储字符串或者整型</p>

<h1 id="二-原理分析">二、原理分析</h1>

<h2 id="1-结构">1. 结构</h2>

<h3 id="listpack结构">listpack结构：</h3>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">&lt;tot-bytes&gt; &lt;num-elements&gt; &lt;element-1&gt; ... &lt;element-N&gt; &lt;listpack-end-byte&gt;</code></pre></div>
<p>listpack由4部分组成：total Bytes、Num Elem、Entry以及End</p>

<ul>
<li>Total Bytes为整个listpack的空间大小，占用4个字节，每个listpack最多占用4294967295Bytes。</li>
<li>Num Elem为listpack中的元素个数，即Entry的个数，占用2个字节，值得注意的是，这并不意味着listpack最多只能存放65535个Entry，当Entry个数大于等于65535时，Num Elem被设置为65535，此时如果需要获取元素个数，需要遍历整个listpack。</li>
<li>Entry为每个具体的元素。</li>
<li>End为listpack结束标志，占用1个字节，内容为0xFF。</li>
</ul>

<h3 id="entry结构">entry结构：</h3>

<p>Entry为listpack中的具体元素，其内容可以为字符串或者整型，每个Entry由<strong>3部分</strong>组成：</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">&lt;encoding-type&gt;&lt;element-data&gt;&lt;element-tot-len&gt;
|                                            |
+--------------------------------------------+
            (This is an element)</code></pre></div>
<p>从组成上可以看出，和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。</p>

<p>不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样，保存其前一个列表项的长度，它只会包含三个方面内容，分别是当前元素的<strong>编码类型</strong>（encoding）、<strong>元素数据</strong> (data)，以及编码类型和元素数据这两部分的<strong>长度</strong> (len)。</p>

<p>其中 type 和 tot-len 一定有值；有时 data 可能会缺失，因为对于一些小的元素可以直接将data放在type字段中。</p>

<p><strong>element-tot-len</strong>记录了这个Entry的长度（encoding + data），注意并不包括 element-tot-len 自身的长度，占用的字节数小于等于5。</p>

<ul>
<li>element-tot-len 所占用的每个字节的第一个 bit 用于标识；0代表结束，1代表尚未结束，每个字节只有7 bit 有效。</li>
<li>值得一提的是，element-tot-len 主要用于<strong>从后向前</strong>遍历，当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的 element-tot-len 字段的结束标识，进而可以计算出上一个元素的长度。</li>
<li>例如 element-tot-len 为0000000110001000，代表该元素的长度为00000010001000，即136字节。通过计算即可算出上一个元素的首地址（entry的首地址）。</li>
</ul>

<p>需要注意的是，在整型存储中，<strong>并不实际存储负数</strong>，而是将负数转换为正数进行存储。例如，在13位整型存储中，存储范围为[0, 8191]，其中[0, 4095]对应非负的[0, 4095]（当然，[0, 127]将会采用7位无符号整型存储），而[4096, 8191]则对应[-4096, -1]。</p>

<h2 id="2-编码方式">2. 编码方式</h2>

<p>encoding-type是理解数据类型的基础，为了节省内存空间，listpack针对不同的数据做了不同的编码：</p>

<h3 id="小的数字">小的数字</h3>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">0|xxxxxxx</code></pre></div>
<p>表示7位无符号整型，后7位为数据。</p>

<p>我们知道，int类型占4字节，字符类型占1字节；因此较小的整型数用字符串表示就可以节省一定的空间；比如，65、1这样的整数，因此，该编码可以用于表示0～127之间的整数。</p>

<h3 id="小的字符串">小的字符串</h3>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">10|xxxxxx &lt;string-data&gt;</code></pre></div>
<p>6位字符串长度，后6位为字符串长度，再之后则是字符串内容（0 ~ 63 bytes）</p>

<h3 id="多字节编码">多字节编码</h3>

<p>如果第一个字节的最高2bit被设置为1，采用如下两种编码方式</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">110|xxxxx yyyyyyyy -- 13 bit signed integer，即13位整型，后5位及下个字节为数据内容
1110|xxxx yyyyyyyy -- string with length up to 4095，即12位长度的字符串，后4位及下个字节为字符串长度，再之后的为字符串数据。</code></pre></div>
<p>如果第一个字节的最高4bit被设置为1，将采用以下几种方式编码</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">1111|0000 &lt;4 bytes len&gt; &lt;large string&gt;，即32位长度字符串，后4字节为字符串长度，再之后为字符串内容
1111|0001 &lt;16 bits signed integer&gt;，即16位整型，后2字节为数据
1111|0010 &lt;24 bits signed integer&gt;，即24位整型，后3字节为数据
1111|0011 &lt;32 bits signed integer&gt;，即32位整型，后4字节为数据
1111|0100 &lt;64 bits signed integer&gt;，即64位整型，后8字节为数据
1111|0101 to 1111|1110 are currently not used.   当前不用编码
1111|1111 End of listpack，结尾标识</code></pre></div>
<h2 id="3-listpack-避免连锁更新的实现方式">3. listpack 避免连锁更新的实现方式</h2>

<p>在 listpack 中，因为每个列表项<strong>只记录自己的长度</strong>，而不会像 ziplist 中的列表项那样，会记录前一项的长度。所以，当在 listpack 中新增或修改元素时，实际上只会涉及每个列表项自己的操作，而不会影响后续列表项的长度变化，这就避免了<strong>连锁更新</strong>。</p>

<p>如果 listpack 列表项只记录当前项的长度，那么 listpack 支持从左向右<strong>正向查询</strong>列表，或是从右向左<strong>反向查询</strong>列表吗？</p>

<p>来，继续往下看～</p>

<h2 id="4-查询">4. 查询</h2>

<h3 id="正向查询">正向查询</h3>

<p>首先，listpack 保存了 LP_HDR_SIZE，通过该参数可以直接将指针移动到第一个 entry 列表项</p>

<ul>
<li>先计算 encoding + data 的总长度 len1</li>
<li>通过 len1 可计算出 element-tot-len 的长度</li>
<li>len1 + element-tot-len 之和即为 entry 总长度 total-len</li>
<li>向后移动 total-len 即为下一个列表项的起始位置</li>
</ul>

<p>这就是正向查询的过程。</p>

<h3 id="反向查询">反向查询</h3>

<p>为了<strong>支持反向查询</strong>，特意设计了参数element-tot-len，怎么说呢？因为对于正向查询，encoding保存了数据类型及数据长度，就可以知道整个entry的长度</p>

<p><strong>element-tot-len</strong>的特殊编码方式：element-tot-len 每个字节的最高位，是用来表示当前字节是否为 element-tot-len 的最后一个字节，这里存在两种情况，分别是：</p>

<ul>
<li>最高位为 1，表示 element-tot-len 还没有结束，当前字节的左边字节仍然表示 element-tot-len 的内容；</li>
<li>最高位为 0，表示当前字节已经是 element-tot-len 最后一个字节了。而 element-tot-len 每个字节的低 7 位，则记录了实际的长度信息。</li>
</ul>

<p>这里需要注意的是，element-tot-len 每个字节的低 7 位采用了<strong>大端模式存储</strong>，也就是说，entry-len 的低位字节保存在内存高地址上。</p>

<p>正是因为有了 element-tot-len 的特别编码方式，lpDecodeBacklen 函数就可以从当前列表项起始位置的指针开始，向左逐个字节解析，得到前一项的 element-tot-len 值，也就可以得到encoding + data的总长度，从而得出entry的总长度；减去entry的总长度，就得到了前一个entry的地址～</p>

<h1 id="源码分析">源码分析</h1>

<h2 id="1-初始化">1、初始化</h2>

<p>lpNew 函数创建了一个空的 listpack，一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中，它默认是 6 个字节，其中 4 个字节是记录 listpack 的总字节数，2 个字节是记录 listpack 的元素数量。</p>

<p>此外，listpack 的最后一个字节是用来标识 listpack 的结束，其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样，LP_EOF 的值也是 255</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-cpp" data-lang="cpp"><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpNew</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">void</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lp_malloc</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">LP_HDR_SIZE</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000">lpSetTotalBytes</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">LP_HDR_SIZE</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000">lpSetNumElements</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000">lp</span><span style="color:#000;font-weight:bold">[</span><span style="color:#000">LP_HDR_SIZE</span><span style="color:#000;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_EOF</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#000">lp</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span>
</code></pre></div>
<p>来，再来回顾下listpack组成结构：</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-text" data-lang="text">&lt;tot-bytes&gt; &lt;num-elements&gt; &lt;element-1&gt; ... &lt;element-N&gt; &lt;listpack-end-byte&gt;
|------ LP_HDR_SIZE -----|                             |---- 末尾标志 -----|</code></pre></div>
<h2 id="2-增删改操作">2、增删改操作</h2>

<p>listpack提供了2种<strong>添加元素</strong>的方式：一种是在<strong>任意位置插入</strong>元素，一种是在<strong>末尾插入</strong>元素。在末尾插入元素的底层实现通过调用任意位置插入元素进行，具体实现为lpInsert函数。</p>

<p>listpack的<strong>删除操作</strong>被转换为用空元素替换的操作。</p>

<p>listpack的<strong>替换操作</strong>（即改操作）的底层实现也是通过lpInsert函数实现的。函数定义如下：</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-cpp" data-lang="cpp"><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpInsert</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">uint32_t</span> <span style="color:#000">size</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">where</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">newp</span><span style="color:#000;font-weight:bold">)</span> 
</code></pre></div>
<p>其中：</p>

<ul>
<li>lp为当前待操作的 listpack；</li>
<li>ele 为待插入的新元素或者待替换的新元素，ele 为空时，也就是删除操作；</li>
<li>size 为 ele 的长度；</li>
<li>p为待插入的位置或者带替换的元素位置；</li>
<li>where 有 LP_BEFORE（前插）、LP_AFTER（后插）、LP_REPLACE（替换）；</li>
<li>*newp 用于返回插入的元素、替换的元素、删除元素的下一个元素。</li>
</ul>

<p>来，具体看看源码实现：</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-cpp" data-lang="cpp"><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpInsert</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">uint32_t</span> <span style="color:#000">size</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">where</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">newp</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#000">intenc</span><span style="color:#000;font-weight:bold">[</span><span style="color:#000">LP_MAX_INT_ENCODING_LEN</span><span style="color:#000;font-weight:bold">]</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#000">backlen</span><span style="color:#000;font-weight:bold">[</span><span style="color:#000">LP_MAX_BACKLEN_SIZE</span><span style="color:#000;font-weight:bold">]</span><span style="color:#000;font-weight:bold">;</span>

    <span style="color:#204a87;font-weight:bold">uint64_t</span> <span style="color:#000">enclen</span><span style="color:#000;font-weight:bold">;</span> <span style="color:#8f5902;font-style:italic">/* The length of the encoded element. */</span>
    <span style="color:#8f5902;font-style:italic">// 当ele为null时意味着删除, 也就是用null替换原来的ele
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">ele</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000">where</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_REPLACE</span><span style="color:#000;font-weight:bold">;</span>
    
    <span style="color:#8f5902;font-style:italic">// 如果是在当前元素之后插入的话，那么可以将指针移动到下一个元素，也就是变成了下一个元素的LP_BEFORE操作；因此实际上只剩两种操作，LP_BEFORE and LP_REPLACE
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">where</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_AFTER</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#000">p</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lpSkip</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">where</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_BEFORE</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">ASSERT_INTEGRITY</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>
    
    <span style="color:#8f5902;font-style:italic">// 先存下元素的offset，当内存重分配之后可以重新定位p
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">long</span> <span style="color:#000">poff</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">p</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">lp</span>
    
    <span style="color:#8f5902;font-style:italic">// 得到编码类型，LP_ENCODING_INT or LP_ENCODING_STR
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">enctype</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#000">enctype</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lpEncodeGetType</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">size</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">intenc</span><span style="color:#000;font-weight:bold">,</span><span style="color:#ce5c00;font-weight:bold">&amp;</span><span style="color:#000">enclen</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#000">enctype</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">enclen</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>

    <span style="color:#8f5902;font-style:italic">/* We need to also encode the backward-parsable length of the element
</span><span style="color:#8f5902;font-style:italic">     * and append it to the end: this allows to traverse the listpack from
</span><span style="color:#8f5902;font-style:italic">     * the end to the start. */</span>
    <span style="color:#8f5902;font-style:italic">// backlen_size也就是element-tot-size，得到backlen_size占用的字节数
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">long</span> <span style="color:#000">backlen_size</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">ele</span> <span style="color:#ce5c00;font-weight:bold">?</span> <span style="color:#000">lpEncodeBacklen</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">backlen</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">enclen</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">:</span> <span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">uint64_t</span> <span style="color:#000">old_listpack_bytes</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lpGetTotalBytes</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">uint32_t</span> <span style="color:#000">replaced_len</span>  <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">where</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_REPLACE</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#000">replaced_len</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lpCurrentEncodedSizeUnsafe</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">replaced_len</span> <span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lpEncodeBacklen</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">replaced_len</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">ASSERT_INTEGRITY_LEN</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#000">p</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#000">replaced_len</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>

    <span style="color:#8f5902;font-style:italic">// 计算新空间大小
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">uint64_t</span> <span style="color:#000">new_listpack_bytes</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">old_listpack_bytes</span> <span style="color:#ce5c00;font-weight:bold">+</span> <span style="color:#000">enclen</span> <span style="color:#ce5c00;font-weight:bold">+</span> <span style="color:#000">backlen_size</span>
                                  <span style="color:#ce5c00;font-weight:bold">-</span> <span style="color:#000">replaced_len</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">new_listpack_bytes</span> <span style="color:#ce5c00;font-weight:bold">&gt;</span> <span style="color:#000">UINT32_MAX</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">;</span>

    <span style="color:#8f5902;font-style:italic">// 接下来将会进行内存重分配，扩容或缩容
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">dst</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">+</span> <span style="color:#000">poff</span><span style="color:#000;font-weight:bold">;</span> <span style="color:#8f5902;font-style:italic">/* May be updated after reallocation. */</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">new_listpack_bytes</span> <span style="color:#ce5c00;font-weight:bold">&gt;</span> <span style="color:#000">old_listpack_bytes</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lp_realloc</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">new_listpack_bytes</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">dst</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">+</span> <span style="color:#000">poff</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>

    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">where</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_BEFORE</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#000">memmove</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">dst</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">enclen</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">backlen_size</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">dst</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">old_listpack_bytes</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">poff</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#000;font-weight:bold">{</span> <span style="color:#8f5902;font-style:italic">/* LP_REPLACE. */</span>
        <span style="color:#204a87;font-weight:bold">long</span> <span style="color:#000">lendiff</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">enclen</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">backlen_size</span><span style="color:#000;font-weight:bold">)</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">replaced_len</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">memmove</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">dst</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">replaced_len</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">lendiff</span><span style="color:#000;font-weight:bold">,</span>
                <span style="color:#000">dst</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">replaced_len</span><span style="color:#000;font-weight:bold">,</span>
                <span style="color:#000">old_listpack_bytes</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">poff</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">replaced_len</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>

    <span style="color:#8f5902;font-style:italic">/* Realloc after: we need to free space. */</span>
    <span style="color:#8f5902;font-style:italic">// 缩容
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">new_listpack_bytes</span> <span style="color:#ce5c00;font-weight:bold">&lt;</span> <span style="color:#000">old_listpack_bytes</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lp_realloc</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">new_listpack_bytes</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">dst</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lp</span> <span style="color:#ce5c00;font-weight:bold">+</span> <span style="color:#000">poff</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>

    <span style="color:#8f5902;font-style:italic">/* Store the entry. */</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">newp</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">newp</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">dst</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#8f5902;font-style:italic">/* In case of deletion, set &#39;newp&#39; to NULL if the next element is
</span><span style="color:#8f5902;font-style:italic">         * the EOF element. */</span>
        <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#ce5c00;font-weight:bold">!</span><span style="color:#000">ele</span> <span style="color:#ce5c00;font-weight:bold">&amp;</span><span style="color:#ce5c00;font-weight:bold">&amp;</span> <span style="color:#000">dst</span><span style="color:#000;font-weight:bold">[</span><span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_EOF</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">newp</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">enctype</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_ENCODING_INT</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
            <span style="color:#000">memcpy</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">dst</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">intenc</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">enclen</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#000;font-weight:bold">{</span>
            <span style="color:#000">lpEncodeString</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">dst</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">size</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000;font-weight:bold">}</span>
        <span style="color:#000">dst</span> <span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">enclen</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">memcpy</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">dst</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">backlen</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">backlen_size</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000">dst</span> <span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">backlen_size</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000;font-weight:bold">}</span>

    <span style="color:#8f5902;font-style:italic">/* Update header. */</span>
    <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">where</span> <span style="color:#ce5c00;font-weight:bold">!</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_REPLACE</span> <span style="color:#ce5c00;font-weight:bold">|</span><span style="color:#ce5c00;font-weight:bold">|</span> <span style="color:#000">ele</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
        <span style="color:#204a87;font-weight:bold">uint32_t</span> <span style="color:#000">num_elements</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">lpGetNumElements</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">num_elements</span> <span style="color:#ce5c00;font-weight:bold">!</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_HDR_NUMELE_UNKNOWN</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
            <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">ele</span><span style="color:#000;font-weight:bold">)</span>
                <span style="color:#000">lpSetNumElements</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">num_elements</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
            <span style="color:#204a87;font-weight:bold">else</span>
                <span style="color:#000">lpSetNumElements</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">num_elements</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
        <span style="color:#000;font-weight:bold">}</span>
    <span style="color:#000;font-weight:bold">}</span>
    <span style="color:#000">lpSetTotalBytes</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">new_listpack_bytes</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
 
    <span style="color:#000;font-weight:bold">.</span><span style="color:#000;font-weight:bold">.</span><span style="color:#000;font-weight:bold">.</span>

    <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#000">lp</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span>
</code></pre></div>
<p>该函数返回null或者插入的元素，替换的元素，删除元素的下一个元素。删除或者替换的主要过程如下：</p>

<ul>
<li>计算需要插入的新元素或者替换旧元素的新元素需要的空间；</li>
<li>计算进行插入或者替换后整个 listpack 所需的空间，通过 realloc 申请空间；</li>
<li>调整新的 listpack 中的老的元素的位置，为待操作元素预留空间；</li>
<li>释放旧的 listpack；</li>
<li>在新的 listpack 中进行插入或替换的操作；</li>
<li>更新新的 listpack 结构头部的统计信息。</li>
</ul>

<h2 id="3-遍历操作">3、遍历操作</h2>

<p>listpack 提供了一组接口用于遍历其所有元素，核心思想是利用每个 entry 的 encoding 或者element-tot-len 字段获取当前 entry 的长度，接口实现较为简单。</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-cpp" data-lang="cpp"><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpFirst</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpLast</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpNext</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpPrev</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lp</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
</code></pre></div>
<p>此处获取的仅仅是某个 entry 首地址的指针，如果要读取当前元素则需要使用 lpGet 接口，也就是说 lpFirst、lpLast 等接口负责定位 entry 首地址，lpGet 则负责实际读取操作；</p>

<h2 id="4-读取元素">4、读取元素</h2>

<p>lpGet 用于获取 p 指向的 listpack 中真正存储的元素：</p>

<ul>
<li>当元素采用字符串编码时，返回字符串的第一个元素位置，count 为元素个数；-</li>

<li><p>当采用整型编码时，若 intbuf 不为空，则将整型数据转换为字符串存储在 intbuf 中，count为元素个数，并返回 intbuf。若 intbuf 为空，直接将数据存储在 count 中，返回null。</p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-cpp" data-lang="cpp"><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">lpGet</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">int64_t</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">count</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#204a87;font-weight:bold">unsigned</span> <span style="color:#204a87;font-weight:bold">char</span> <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">intbuf</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
<span style="color:#204a87;font-weight:bold">int64_t</span> <span style="color:#000">val</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#204a87;font-weight:bold">uint64_t</span> <span style="color:#000">uval</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#000">negstart</span><span style="color:#000;font-weight:bold">,</span> <span style="color:#000">negmax</span><span style="color:#000;font-weight:bold">;</span>

<span style="color:#000">assert</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span> <span style="color:#8f5902;font-style:italic">/* assertion for valgrind (avoid NPD) */</span>
<span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">LP_ENCODING_IS_7BIT_UINT</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">[</span><span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">]</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#000">negstart</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">UINT64_MAX</span><span style="color:#000;font-weight:bold">;</span> <span style="color:#8f5902;font-style:italic">/* 7 bit ints are always positive. */</span>
    <span style="color:#000">negmax</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000">uval</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">p</span><span style="color:#000;font-weight:bold">[</span><span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">&amp;</span> <span style="color:#0000cf;font-weight:bold">0x7f</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">LP_ENCODING_IS_6BIT_STR</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">[</span><span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">]</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span> <span style="color:#8f5902;font-style:italic">// 字符串编码类型
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">count</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">LP_ENCODING_6BIT_STR_LEN</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#000">p</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">LP_ENCODING_IS_13BIT_INT</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000">p</span><span style="color:#000;font-weight:bold">[</span><span style="color:#0000cf;font-weight:bold">0</span><span style="color:#000;font-weight:bold">]</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
    
    <span style="color:#000;font-weight:bold">.</span><span style="color:#000;font-weight:bold">.</span><span style="color:#000;font-weight:bold">.</span><span style="color:#000;font-weight:bold">.</span><span style="color:#000;font-weight:bold">.</span>

<span style="color:#000;font-weight:bold">}</span>

<span style="color:#8f5902;font-style:italic">/* We reach this code path only for integer encodings.
</span><span style="color:#8f5902;font-style:italic"> * Convert the unsigned value to the signed one using two&#39;s complement
</span><span style="color:#8f5902;font-style:italic"> * rule. */</span>
<span style="color:#8f5902;font-style:italic">// 只有整型编码能走到这...
</span><span style="color:#8f5902;font-style:italic"></span><span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">uval</span> <span style="color:#ce5c00;font-weight:bold">&gt;</span><span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">negstart</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#8f5902;font-style:italic">/* This three steps conversion should avoid undefined behaviors
</span><span style="color:#8f5902;font-style:italic">     * in the unsigned -&gt; signed conversion. */</span>
    <span style="color:#000">uval</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">negmax</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">uval</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000">val</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">uval</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#000">val</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">val</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#0000cf;font-weight:bold">1</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#000">val</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">uval</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span>

<span style="color:#8f5902;font-style:italic">/* Return the string representation of the integer or the value itself
</span><span style="color:#8f5902;font-style:italic"> * depending on intbuf being NULL or not. */</span>
<span style="color:#204a87;font-weight:bold">if</span> <span style="color:#000;font-weight:bold">(</span><span style="color:#000">intbuf</span><span style="color:#000;font-weight:bold">)</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">count</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">snprintf</span><span style="color:#000;font-weight:bold">(</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">char</span><span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000">intbuf</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000">LP_INTBUF_SIZE</span><span style="color:#000;font-weight:bold">,</span><span style="color:#4e9a06"></span><span style="color:#4e9a06">&#34;</span><span style="color:#4e9a06">%lld</span><span style="color:#4e9a06">&#34;</span><span style="color:#000;font-weight:bold">,</span><span style="color:#000;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">long</span> <span style="color:#204a87;font-weight:bold">long</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000">val</span><span style="color:#000;font-weight:bold">)</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#000">intbuf</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span> <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#000;font-weight:bold">{</span>
    <span style="color:#ce5c00;font-weight:bold">*</span><span style="color:#000">count</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">val</span><span style="color:#000;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87">NULL</span><span style="color:#000;font-weight:bold">;</span>
<span style="color:#000;font-weight:bold">}</span>
<span style="color:#000;font-weight:bold">}</span>
</code></pre></div></li>
</ul>

<p>lpGet的实现较为简单，主要是利用了每个entry的encode字段。</p>

<h1 id="总结">总结</h1>

<p>可以看出，ziplist、quicklist 和 listpack 是 redis 是不断迭代优化的产物。</p>

<p><strong>ziplist</strong> 的不足主要在于当 ziplist 中元素个数过多，它的查找效率就会降低。而且如果在 ziplist 里新增或修改数据，ziplist 占用的内存空间还需要<strong>重新分配</strong>；更糟糕的是，ziplist 新增某个元素或修改某个元素时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起<strong>连锁更新</strong>问题，导致每个元素的空间都要重新分配，这就会导致 ziplist 的访问性能下降。</p>

<p>因此，为解决 ziplist 以上问题，Redis 先是在 <strong>3.0</strong> 版本中设计实现了 <strong>quicklist</strong>。quicklist 结构在 ziplist 基础上，使用链表将 ziplist 串联起来，链表的每个元素就是一个 ziplist。这种设计减少了数据插入时内存空间的重新分配，以及内存数据的拷贝。同时，quicklist 限制了每个节点上 ziplist 的大小，一旦一个 ziplist 过大，就会采用新增 quicklist 节点的方法。</p>

<p>不过，又因为 quicklist 使用 quicklistNode 结构指向每个 ziplist，无疑增加了内存开销。为了减少内存开销，并进一步避免 ziplist 连锁更新问题，Redis 在 <strong>5.0</strong> 版本中，就设计实现了 <strong>listpack</strong> 结构。listpack 结构沿用了 ziplist <strong>紧凑型的内存布局</strong>，把每个元素都紧挨着放置。</p>

<p><strong>综上：</strong></p>

<ul>
<li>要想彻底解决 ziplist <strong>连锁更新</strong>问题，本质上要修改 ziplist 的存储结构，也就是不要让每个元素保存「上一个」元素的长度，因此迭代出了 listpack</li>
<li><strong>listpack</strong> 每个元素项不再保存上一个元素的长度，而是通过记录entry长度以及element-tot-len中特殊的结束符，来保证既可以从前也可以向后遍历</li>
<li>listpack 是为了替代 ziplist 为设计的，但因为 List/Hash/Set/ZSet 都严重依赖 ziplist，所以这个替换之路很漫长，目前只有 Stream 数据类型用到了 listpack</li>
</ul>

<p>相关参考：</p>

<blockquote>
<ul>
<li><a href="https://github.com/antirez/listpack/blob/master/listpack.md">listpack.md</a></li>
<li><a href="https://www.fatalerrors.org/a/redis-source-code-analysis-26-listpack-source-code-analysis.html">Redis source code analysis (26) listpack source code analysis</a></li>
<li><a href="https://blog.csdn.net/ldw201510803006/article/details/122384221?spm=1001.2014.3001.5501">深入分析redis之quicklist，不一样的ziplist使用方式？</a></li>
<li>[redis压缩列表ziplist，内存优化之路？](</li>
</ul>
</blockquote>

    </div>
    <footer class="post-footer">
     

     <div class="post-nav">
    <div class="post-nav-next post-nav-item">
    
        <a href="http://www.shutdown.cn/post/redis6%E7%94%9F%E4%BA%A7%E9%85%8D%E7%BD%AE/" rel="next" title="">
        <i class="fa fa-chevron-left"></i> 
        </a>
    
    </div>

    <div class="post-nav-prev post-nav-item">
    
        <a href="http://www.shutdown.cn/post/redis7.0%E6%96%B0%E7%89%B9%E6%80%A7-listpack%E6%9B%BF%E6%8D%A2ziplist/" rel="prev" title="">
         <i class="fa fa-chevron-right"></i>
        </a>
    
    </div>
</div>
      
     
     
     






    </footer>
  </article>
</section>

          </div>
        </div>
        <div class="sidebar-toggle">
  <div class="sidebar-toggle-line-wrap">
    <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
    <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
    <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
  </div>
</div>
<aside id="sidebar" class="sidebar">
  <div class="sidebar-inner">

    <section class="site-overview sidebar-panel  sidebar-panel-active ">
      <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image"
        src="http://www.shutdown.cn/img/author.jpg"
        alt="不与天斗Domino" />
    <p class="site-author-name" itemprop="name">不与天斗Domino</p>
    <p class="site-description motion-element" itemprop="description"> 
        Programmer &amp; Architect</p>
</div>
      <nav class="site-state motion-element">
    <div class="site-state-item site-state-posts">
      <a href="http://www.shutdown.cn/post/">
        <span class="site-state-item-count">183</span>
        <span class="site-state-item-name">日志</span>
      </a>
    </div>
    <div class="site-state-item site-state-categories">    
        <a href="http://www.shutdown.cn/categories/">      
         
        <span class="site-state-item-count">15</span>
        
        <span class="site-state-item-name">分类</span>
        
        </a>
    </div>

    <div class="site-state-item site-state-tags">
        <a href="http://www.shutdown.cn/tags/">
         
        <span class="site-state-item-count">224</span>
        
        <span class="site-state-item-name">标签</span>
        </a>
    </div>
</nav>
      
      

      

      <div class="links-of-blogroll motion-element inline">
<script type="text/javascript" src="//rf.revolvermaps.com/0/0/8.js?i=&amp;m=0&amp;s=220&amp;c=ff0000&amp;cr1=ffffff&amp;f=arial&amp;l=33&amp;bv=35" async="async"></script>
</div>

    </section>
    
  </div>
</aside>

      </div>
    </main>
   
    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  <span itemprop="copyrightYear">  &copy; 
  2013 - 2023</span>
  <span class="with-love"><i class="fa fa-heart"></i></span>
  <span class="author" itemprop="copyrightHolder">天地维杰网</span>
  <span class="icp" itemprop="copyrightHolder"><a href="https://beian.miit.gov.cn/" target="_blank">京ICP备13019191号-1</a></span>
</div>
<div class="powered-by">
  Powered by - <a class="theme-link" href="http://gohugo.io" target="_blank" title="hugo" >Hugo v0.63.2</a>
</div>
<div class="theme-info">
  Theme by - <a class="theme-link" href="https://github.com/xtfly/hugo-theme-next" target="_blank"> NexT
  </a>
</div>


      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
      <span id="scrollpercent"><span>0</span>%</span>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/jquery/index.js?v=2.1.3"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/fastclick/lib/fastclick.min.js?v=1.0.6"></script> 
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/velocity/velocity.min.js?v=1.2.1"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/velocity/velocity.ui.min.js?v=1.2.1"></script>
<script src="http://www.shutdown.cn/js/vendor/ua-parser-js/dist/ua-parser.min.js?v=0.7.9"></script>

<script src="http://www.shutdown.cn/js/vendor/fancybox/jquery.fancybox.pack.js?v=2.1.5"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/utils.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/motion.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/affix.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/schemes/pisces.js"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/scrollspy.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/post-details.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/toc.js"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/bootstrap.js"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js"],
    jax: ["input/TeX", "output/HTML-CSS"],
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true
    },
    "HTML-CSS": { fonts: ["TeX"] }
  });
</script>
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML' async></script>
</body>
</html>